package com.lga.algorithm;

import java.util.*;

/**
 *7-2 一元多项式的乘法与加法运算
 * @author lga
 */
public class OneVariablePolynomial {

    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        //输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数
        // （绝对值均为不超过1000的整数）。数字间以空格分隔。
        String variablePolynomialOne = input.nextLine();
        String variablePolynomialTwo = input.nextLine();
        String[] variablePolynomialArrayOne = variablePolynomialOne.split("\\s+");
        String[] variablePolynomialArrayTwo = variablePolynomialTwo.split("\\s+");

        //定义第一个多项式的集合
        List<VariablePolynomial> variablePolynomialListOne = new ArrayList<>();
        List<VariablePolynomial> variablePolynomialListTwo = new ArrayList<>();
        List<VariablePolynomial> finallyMultiplyResult = new ArrayList<>();
        List<VariablePolynomial> addResult = new ArrayList<>();

        //获取两个多项式的对应的集合
        for (int i = 1; i < variablePolynomialArrayOne.length; i++,i++) {
            VariablePolynomial variablePolynomial = new VariablePolynomial();
            try {
                variablePolynomial.setA(Integer.parseInt(variablePolynomialArrayOne[i]));
                variablePolynomial.setY(Integer.parseInt(variablePolynomialArrayOne[i+1]));
            } catch (NumberFormatException e) {
                e.printStackTrace();
            }
            variablePolynomialListOne.add(variablePolynomial);
        }
        for (int i = 1; i < variablePolynomialArrayTwo.length; i++,i++) {
            VariablePolynomial variablePolynomial = new VariablePolynomial();
            variablePolynomial.setA(Integer.parseInt(variablePolynomialArrayTwo[i]));
            variablePolynomial.setY(Integer.parseInt(variablePolynomialArrayTwo[i+1]));
            variablePolynomialListTwo.add(variablePolynomial);
        }

        //获取多项式相乘操作后的结果
        finallyMultiplyResult = getMultiplyResult(variablePolynomialListOne, variablePolynomialListTwo);
        //合并
        finallyMultiplyResult = getMergeResult(finallyMultiplyResult);
        for (VariablePolynomial variablePolynomial : finallyMultiplyResult) {
            System.out.print(variablePolynomial.getA()+" "+variablePolynomial.getY()+" ");
        }
        System.out.println();
        //获取相加后的结果
        addResult = getAddResult(variablePolynomialListOne, variablePolynomialListTwo);
        for (VariablePolynomial variablePolynomial : addResult) {
            System.out.print(variablePolynomial.getA()+" "+variablePolynomial.getY()+" ");
        }

    }

    /**
     * 合并
     */
    private static List getMergeResult(List<VariablePolynomial> finallyMultiplyResult) {
        List<VariablePolynomial> mergeResult = new ArrayList<>();
        //用于保存需要去掉的多项式下标
        ArrayList<Integer> removeOneList = new ArrayList<>();
        for (int i = 0; i < finallyMultiplyResult.size(); i++) {
            for (int j = i+1; j < finallyMultiplyResult.size(); j++) {
                if (finallyMultiplyResult.get(i).getY() == finallyMultiplyResult.get(j).getY()) {
                    removeOneList.add(i);
                    removeOneList.add(j);
                    VariablePolynomial variablePolynomial = new VariablePolynomial();
                    int newA = finallyMultiplyResult.get(i).getA() + finallyMultiplyResult.get(j).getA();
                    variablePolynomial.setA(newA);
                    variablePolynomial.setY(finallyMultiplyResult.get(i).getY());
                    mergeResult.add(variablePolynomial);
                }
            }
        }
        //移除已经合并的下标
        //中间临时变量list，用于删除多余的合并项
        List<VariablePolynomial> tempList01 = new ArrayList(Arrays.asList(new Object[finallyMultiplyResult.size()]));;
        Collections.copy(tempList01,finallyMultiplyResult);
        for (Integer index : removeOneList) {
            finallyMultiplyResult.remove(tempList01.get(index));
        }
        mergeResult.addAll(finallyMultiplyResult);
        Collections.sort(mergeResult);

        return mergeResult;

    }


        /**
         * 相加操作(合并操作)
         */
    private static List getAddResult(List<VariablePolynomial> variablePolynomialListOne, List<VariablePolynomial> variablePolynomialListTwo) {
        List<VariablePolynomial> addResult = new ArrayList<>();
        //用于保存需要去掉的多项式下标
        ArrayList<Integer> removeOneList = new ArrayList<>();
        ArrayList<Integer> removeTwoList = new ArrayList<>();

        for (int i = 0; i < variablePolynomialListOne.size(); i++) {
            for (int j = 0; j < variablePolynomialListTwo.size(); j++) {
                if (variablePolynomialListOne.get(i).getY() == variablePolynomialListTwo.get(j).getY()) {
                    removeOneList.add(i);
                    removeTwoList.add(j);
                    VariablePolynomial variablePolynomial = new VariablePolynomial();
                    int newA = variablePolynomialListOne.get(i).getA() + variablePolynomialListTwo.get(j).getA();
                    variablePolynomial.setA(newA);
                    variablePolynomial.setY(variablePolynomialListOne.get(i).getY());
                    addResult.add(variablePolynomial);
                }
            }
        }
        //移除已经合并的下标
        //中间临时变量list，用于删除多余的合并项
        List<VariablePolynomial> tempList01 = new ArrayList(Arrays.asList(new Object[variablePolynomialListOne.size()]));;
        Collections.copy(tempList01,variablePolynomialListOne);
        for (Integer index : removeOneList) {
            variablePolynomialListOne.remove(tempList01.get(index));
        }
        List<VariablePolynomial> tempList02 = new ArrayList(Arrays.asList(new Object[variablePolynomialListTwo.size()]));;
        Collections.copy(tempList02,variablePolynomialListTwo);
        for (Integer index : removeTwoList) {
            variablePolynomialListTwo.remove(tempList02.get(index));
        }
        addResult.addAll(variablePolynomialListOne);
        addResult.addAll(variablePolynomialListTwo);
        Collections.sort(addResult);

        return addResult;
    }

    /**
     * 相乘操作
     */
    private static List getMultiplyResult(List<VariablePolynomial> variablePolynomialListOne, List<VariablePolynomial> variablePolynomialListTwo) {
        //保存相乘后的多项式集合
        List<VariablePolynomial> multiplyResult = new ArrayList<>();
        List<VariablePolynomial> finallyMultiplyResult = new ArrayList<>();

        for (int i = 0; i < variablePolynomialListOne.size(); i++) {
            for (int j = 0; j < variablePolynomialListTwo.size(); j++) {
                int a = variablePolynomialListOne.get(i).getA() * variablePolynomialListTwo.get(j).getA();
                int y = variablePolynomialListOne.get(i).getY() + variablePolynomialListTwo.get(j).getY();
                VariablePolynomial variablePolynomialMultiplyResult = new VariablePolynomial();
                variablePolynomialMultiplyResult.setA(a);
                variablePolynomialMultiplyResult.setY(y);
                multiplyResult.add(variablePolynomialMultiplyResult);
            }
        }
        //排序
        Collections.sort(multiplyResult);

        return multiplyResult;
    }

    /**
     * 多项式类
     */
    static class VariablePolynomial implements Comparable<VariablePolynomial>{
        /**
         * 多项式常数项
         */
       private int a;

        /**
         * 多项式次数项
         */
        private int y;

        public int getA() {
            return a;
        }

        public void setA(int a) {
            this.a = a;
        }

        public int getY() {
            return y;
        }

        public void setY(int y) {
            this.y = y;
        }

        @Override
        public String toString() {
            return "(" + a + "," + y + ")";
        }


        @Override
        public int compareTo(VariablePolynomial o) {
            return o.getY()-this.getY();
        }
    }
}
